package com.mapbar.ure;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

import com.mapbar.ure.backend.DFA;
import com.mapbar.ure.backend.NFA;
import com.mapbar.ure.backend.converter.NFA2DFAConverter;
import com.mapbar.ure.backend.converter.REAST2NFAConverter;
import com.mapbar.ure.frontend.lr1.Grammar;
import com.mapbar.ure.frontend.lr1.Production;
import com.mapbar.ure.frontend.parser.AST;
import com.mapbar.ure.frontend.parser.Parser;

/**
 * <h1>通用模式匹配模块，用于对标注结果进行模式匹配。</h1> <br>
 * 
 * <h2>使用简介</h2>
 * 
 * 内部使用的匹配语法为正则表达式。目前支持正则表达式的三个核心语法： 连接，选择，闭包。 这三个语法在正则表达式中为: ab, a|b,
 * a*。为了额外支持语法优先级，另外还包括括号操作。<br>
 * <p>
 * 
 * 由于提供了类型灵活性，用户需要提供自己的泛型类型和正则表达式的对应关系，需要提供的内容如下，具体代码类型是
 * {@code HashMap<T, ProductionType>}
 * <p>
 * 
 * ProductionType.OpeningParenthesis; 左括号<br>
 * ProductionType.ClosingParenthesis; 右括号<br>
 * ProductionType.Cons; 连接操作<br>
 * ProductionType.Closure; 闭包操作<br>
 * ProductionType.Or; 选择操作<br>
 * ProductionType.AvailableCharSet; 参与匹配的字符集<br>
 * ProductionType.EOF; 结果标识，需要加到所有<tt>pattern</tt>的最后<br>
 * 
 * <p>
 * 在构造函数中对 <tt>pattern</tt> 的语法分析阶段，如果有不符合语法的内容，会有 {@link ASTException}
 * 的异常抛出，其中存储了错误的位置。为控制复杂度，目前只支持每次编译返回一个语法错误。
 * <h2>注意事项</h2>
 * 这里的连接操作在pattern中需要显式表达，以方便语法分析。正则中ab需要写为a+b,
 * 如需在自己的语法中支持隐式的连接操作让配置文件更清晰，可以参考语法扩展部分中的方法。
 * <h2>语法扩展</h2>
 * 
 * 由于支持的范围限定于正则表达式的三个核心语法，所以如现有的正则表达式的语法扩展可能需要自我实现，这些基本都属于语法糖范围，
 * 大部分都可以在实施match前进行简单的替换而提供支持。
 * <p>
 * 
 * <i>行首，行尾</i><br>
 * 可以在AvailableCharSet中加入两个正常匹配外的项，一个代表行首，一个代表行尾，在match前，分别在List头尾各加入两者。
 * <p>
 * <i>通配符</i> <br>
 * 比如 {@code REU<Character>}
 * 设定"～"为"0-9"的通配符,在match前，将"~"都替换为"(0|1|2|3|4|5|6|7|8|9)"即可。
 * <p>
 * <i>隐式连接操作</i><br>
 * pattern可以写显式连接操作，在match前，将需要显式连接操作的地方补全即可。
 * 
 * @param <T>
 *            模式匹配的类型，如果使用 {@link Character}则相当于正则表达式。
 * 
 * @author QIN Jian
 * @see ProductionType
 * @see ASTException
 * 
 */
public class URE<T> {
	public static void main(String[] args) {
		charDemo();
		System.out.println("charDemo() finished.");
		intDemo();
		System.out.println("intDemo() finished.");
	}

	private static void intDemo() {
		/**
		 * 以下为各项准备
		 */
		HashMap<Integer, ProductionType> k2t = new HashMap<Integer, ProductionType>();
		k2t.put(-1, ProductionType.OpeningParenthesis);
		k2t.put(-2, ProductionType.ClosingParenthesis);
		k2t.put(-3, ProductionType.Cons);
		k2t.put(-4, ProductionType.Closure);
		k2t.put(-5, ProductionType.Or);
		k2t.put(0, ProductionType.AvailableCharSet);
		k2t.put(1, ProductionType.AvailableCharSet);
		k2t.put(2, ProductionType.AvailableCharSet);
		k2t.put(3, ProductionType.AvailableCharSet);
		k2t.put(4, ProductionType.AvailableCharSet);
		k2t.put(5, ProductionType.AvailableCharSet);
		k2t.put(6, ProductionType.AvailableCharSet);
		k2t.put(7, ProductionType.AvailableCharSet);
		k2t.put(8, ProductionType.AvailableCharSet);
		k2t.put(9, ProductionType.AvailableCharSet);
		k2t.put(-100, ProductionType.EOF);

		List<Integer> pattern = new ArrayList<Integer>();
		Integer[] in = { 0, -3, 1, -3, 8, -3, 9, -3, -1, 0, -5, 2, -5, 4, -2 };
		for (Integer i : in) {
			pattern.add(i);
		}

		/**
		 * 以下为REU的生成和编译
		 */
		URE<Integer> reu = null;
		try {
			reu = new URE<>(pattern, k2t);
		} catch (ASTException e) {
			System.out.print("AST生成错误，位置：" + e.getErrorPosition());
			e.printStackTrace();
		}

		/**
		 * 以下为匹配测试。
		 */
		Integer ss[][] = new Integer[][] { { 0, 1, 8, 9, 4 }, { 1, 1 },
				{ 9, 4 }, { 0, 1, 8, 9, 0 }, { 0, 1, 8, 9, 5 } };
		for (Integer[] s : ss) {
			System.out.println("==================");
			System.out.print("匹配：");
			for (Integer i : s) {
				System.out.print(" " + i);
			}
			System.out.print('\n');
			List<Integer> i = new ArrayList<Integer>();
			for (Integer c : s) {
				i.add(c);
			}

			if (reu.match(i) == s.length) {
				System.out.println("匹配成功。");
			} else {
				System.out.print("匹配失败位置：");
				System.out.println(reu.match(i));
			}
		}
		System.out.println("==================");
	}

	private static void charDemo() {
		/**
		 * 以下为各项准备
		 */
		HashMap<Character, ProductionType> k2t = new HashMap<Character, ProductionType>();
		k2t.put('(', ProductionType.OpeningParenthesis);
		k2t.put(')', ProductionType.ClosingParenthesis);
		k2t.put('+', ProductionType.Cons);
		k2t.put('*', ProductionType.Closure);
		k2t.put('|', ProductionType.Or);
		k2t.put('0', ProductionType.AvailableCharSet);
		k2t.put('1', ProductionType.AvailableCharSet);
		k2t.put('2', ProductionType.AvailableCharSet);
		k2t.put('3', ProductionType.AvailableCharSet);
		k2t.put('4', ProductionType.AvailableCharSet);
		k2t.put('5', ProductionType.AvailableCharSet);
		k2t.put('6', ProductionType.AvailableCharSet);
		k2t.put('7', ProductionType.AvailableCharSet);
		k2t.put('8', ProductionType.AvailableCharSet);
		k2t.put('9', ProductionType.AvailableCharSet);
		k2t.put('.', ProductionType.AvailableCharSet);
		k2t.put('_', ProductionType.EOF);

		List<Character> pattern = new ArrayList<Character>();
		String input = "(0|1|2|3|4|5|6|7|8|9)+.+(0|1|2|3|4|5|6|7|8|9)+(0|1|2|3|4|5|6|7|8|9)";
		input = "(1|2|3)+.+(2|3)*+4+5";
		for (char c : input.toCharArray()) {
			pattern.add(c);
		}

		/**
		 * 以下为REU的生成和编译
		 */
		URE<Character> reu = null;
		try {
			reu = new URE<>(pattern, k2t);
		} catch (ASTException e) {
			System.out.print("AST生成错误，位置：" + e.getErrorPosition());
			e.printStackTrace();
		}

		/**
		 * 以下为匹配测试。
		 */
		String ss[] = new String[] { "0.12", "1.232333245", "3.12", "32.12" };
		for (String s : ss) {
			System.out.println("==================");
			System.out.println("匹配：");
			List<Character> i = new ArrayList<Character>();
			for (char c : s.toCharArray()) {
				i.add(c);
			}
			if (reu.match(i) == s.length()) {
				System.out.println("匹配成功。");
			} else {
				System.out.print("匹配失败位置：");
				System.out.println(reu.match(i));
			}
		}
		System.out.println("==================");
	}

	private DFA<T> dfa;
	private List<T> pattern;

	/**
	 * 生成REU，pattern会在构造过程中进行编译，如出现语法错误会有异常抛出
	 * 
	 * @param pattern
	 *            满足正则表达式语法的pattern
	 * @param k2t
	 *            用户定义的类型和正则表达式的语法生成式的对应关系
	 * @throws ASTException
	 *             生成抽象语法树时语法检查不通过，存储了错误位置,可以利用 {@code getErrorPosition()}
	 *             获得语法错误发生的位置。
	 */
	public URE(List<T> pattern, HashMap<T, ProductionType> k2t)
			throws ASTException {
		for (T key : k2t.keySet()) {
			if (k2t.get(key).equals(ProductionType.EOF)) {
				pattern.add(key);
			}
		}

		this.pattern = pattern;
		dfa = compile(buildReGrammar(), pattern, k2t);
	}

	private DFA<T> compile(Grammar reGrammar, List<T> pattern,
			HashMap<T, ProductionType> k2t) throws ASTException {
		Parser<T> parser = new Parser<T>(reGrammar);
		AST<T> ast = parser.parse(pattern, k2t);

		REAST2NFAConverter<T> nfaConverter = new REAST2NFAConverter<T>();
		NFA<T> nfa = nfaConverter.convert(ast);

		NFA2DFAConverter<T> dfaConverter = new NFA2DFAConverter<T>();
		HashSet<T> alphabet = getAlphabet(k2t);
		DFA<T> dfa = dfaConverter.subsetConstruction(alphabet, nfa);

		return dfa;
	}

	private HashSet<T> getAlphabet(HashMap<T, ProductionType> k2t) {
		HashSet<T> ret = new HashSet<T>();
		for (T key : k2t.keySet()) {
			if (ProductionType.isAvailableCharSet(k2t.get(key))) {
				ret.add(key);
			}
		}
		return ret;
	}

	private Grammar buildReGrammar() {
		Grammar g = new Grammar();
		// RE语法
		g.addProduction(new Production(ProductionType.Goal,
				new ProductionType[][] { { ProductionType.RE } }));
		g.addProduction(new Production(ProductionType.RE,
				new ProductionType[][] {
						{ ProductionType.RE, ProductionType.Or,
								ProductionType.T }, { ProductionType.T } }));
		g.addProduction(new Production(ProductionType.T,
				new ProductionType[][] {
						{ ProductionType.T, ProductionType.Cons,
								ProductionType.A }, { ProductionType.A } }));
		g.addProduction(new Production(ProductionType.A,
				new ProductionType[][] {
						{ ProductionType.F, ProductionType.Closure },
						{ ProductionType.F } }));
		g.addProduction(new Production(ProductionType.F,
				new ProductionType[][] {
						{ ProductionType.OpeningParenthesis, ProductionType.RE,
								ProductionType.ClosingParenthesis },
						{ ProductionType.AvailableCharSet } }));
		g.buildLR1Table();
		return g;
	}

	/**
	 * 匹配input中的参数
	 * 
	 * @param input
	 * @return 匹配的位置，成功则为 input.size(); 失败则返回匹配失败的位置。
	 */
	public int match(List<T> input) {
		return dfa.match(input);
	}

	public List<T> getPattern() {
		return pattern;
	}
}
